1000 500
790529097 434885349 531235926 409035649 921970212 919128160 899057862 213257504 962485345 91874772 326546683 83969415 315621576 345151599 745488728 466617816 571417013 444207770 413389189 173313995 482892532 884403794 458042459 135979689 95873413 739791215 895597985 748170235 184592407 687338185 647464152 80754031 697118563 619987244 923595962 582363893 658712898 368088948 330222479 465117130 991152180 991098829 450848914 781442570 566758566 575324947 4766632 55267400 385919007 608260775 458731578 672635146 433177551 88212069 527819860 38245068 919875919 53392988 986974106 540406069 386798592 330865758 989131744 279543942 937516443 439094105 661579856 809986047 859200071 156019669 856863346 513088660 751113873 776848403 534780590 724644187 826282847 473860496 882838393 965614844 464323184 10601185 865743912 242399940 843322961 169710659 342177337 796885308 923525370 854312290 321214748 724784037 536631640 303300289 593698917 156534400 706188502 232022269 698741501 21528023 2408803 338677349 308762184 637779233 674082799 792451952 391038504 830869264 102122852 544464771 508940602 307921209 304492359 837162111 402424951 577836594 201503822 435289117 98175057 106680861 144761410 13281554 911049083 306994810 667257224 105331475 910430074 994507210 932319812 715095440 303910695 251816201 957314920 658071494 842799482 82111372 972013527 941046573 822186432 325019500 411339628 995864090 619986523 802590287 66290111 192130135 726130750 551836727 985411549 239728943 995858121 174950406 296168448 187147430 188908076 920545844 776231064 437470722 285389269 717060677 70093961 694912620 536182943 296808186 815629337 858606725 73257500 742749719 229615188 823251208 725500002 737691814 845558050 469240841 596715405 190224332 4244101 853854187 363489485 954929419 403819366 271520532 159764324 243458975 97577023 62066808 362722503 576183011 619499001 832968841 930042801 205256771 408747218 8233912 314617042 50001222 901902419 60830244 827357642 366596819 951114933 17187980 471321107 105606086 613249743 838935821 508484157 604490742 113306625 466579156 805167161 784638641 154110635 114810949 858859821 777285770 910140556 191821350 980082563 4752880 377355047 125653699 976040160 785029121 541852373 155212168 962255282 276770241 590560793 155035111 432134460 29804709 333167588 781698814 781801458 576667413 446217562 671561658 918482066 929289574 448241915 416136683 4830065 480691709 349496810 234647543 658029980 240671519 990185922 659323202 811603350 471314360 619461786 138521135 886751115 572746919 511895113 28350891 510181640 952913466 376643550 732330485 146902104 89471630 520920679 557853326 527057517 991820211 332893714 380183836 28743928 510998505 110183778 705260924 283531731 110829730 81412274 911933442 875828700 473845451 458689835 119683614 915405874 608998870 597509078 414503632 771406402 373455463 962542321 646687257 995249927 130778566 609043195 800148457 294067418 205757773 606532522 513154341 410564192 782677962 768055739 347711416 463166 619274623 117481123 274016462 674827446 245777663 944469835 821031170 167425762 916118905 875366673 427752191 897048606 504174717 24005203 897544209 862212396 486296558 451526600 429800907 541589560 893550816 298814787 566362805 671317871 848237695 337299512 63780891 217262976 989786121 213428752 623336333 26030690 274525140 292203358 227350347 92869126 279478308 929030486 704166969 226017913 636194931 575408740 455788139 145710839 71232539 343155435 969910927 754720964 156299681 792387823 877231481 992599106 126274294 780109963 424980872 775503775 966885493 542137224 391916387 797437031 209175840 857310769 977500116 482808471 740269843 800230708 595691500 830724391 863943969 606540481 985402561 647133946 570568189 939869351 835322472 197214663 199810719 202274709 227293146 63636766 360427014 295926218 326600129 934545432 106100839 437698214 633584602 696301941 264944278 687917960 724023419 752855651 846511500 306509079 536528592 157690493 625417092 365445979 924334788 846201130 437960533 894201187 219994669 986605081 698628297 250787384 950403629 789929209 529358799 212800102 934442340 942818101 234233292 421788248 712181912 913910850 597908041 5020501 802381364 175420069 900815656 554595392 146273999 993167023 939389661 534938014 939456437 482486614 211603729 972051304 633729744 859032973 682965009 260316894 479031886 941273125 417092878 77810924 351889267 589497169 873687318 165352255 281368272 432651955 894285141 879371341 907433821 827859041 152054518 855233268 90092245 917154731 230946430 558421752 78370044 380112101 233400006 270926385 764169210 850291622 486897515 139501891 627625178 469182862 81578012 253997482 679940806 209109652 195160971 357618496 675022938 222712539 394128414 805940735 611079347 481031239 255552816 968466747 165170997 222735608 199484950 106521629 631179718 4917198 791318134 906012605 798644757 584684460 884086755 557135828 655738100 65456941 795542046 34940023 465156905 442636576 439295240 282511676 603578298 593869883 896078923 860335932 974451034 545853945 540217479 13468560 950023618 226552446 424885887 940088719 498854003 252825565 531331079 759163400 114262530 582884492 536681735 399194249 957680518 708165983 688492431 446640356 909729997 997728094 677666423 164923161 786255635 733580766 291355726 664238923 552455951 837737077 894200905 295707820 850106594 53771900 837751950 318029860 865133151 897935424 303496131 236986284 397793673 577163967 750309533 912101841 437006452 780341727 209705189 461711888 930763727 115983582 114079638 429239081 986363428 385066192 272334660 727298664 861091319 105022277 150466225 170529633 393923772 265298303 83450104 289231646 734785296 924284687 324873912 600587445 567420131 373808472 506029195 397880961 458310302 69848230 95964157 132833056 658567493 421750025 379115020 224318275 286611852 268784106 111780063 103491139 268689961 672517590 473614587 828662759 638883507 56795435 264628947 102646675 500525484 830147766 500177272 351407154 877333477 32150415 838392531 528498967 82020919 858999930 990808303 435127329 386530064 40180712 433288674 97229184 270835492 397280389 260610904 317783143 872285004 890255067 723007683 468865263 563056125 517522773 81011495 8837203 256303839 762191274 316113186 310550731 481282113 133603353 671651855 317885029 998352565 266379129 73172208 15896570 816076377 104562614 701559351 604241403 638130708 614697551 478761603 206461085 259534247 357498193 279431912 215486862 359584185 635150658 68228244 126895977 228233941 76215473 568614226 888093826 246206136 503147562 798766354 638252470 179841032 6590417 47238115 305167822 551321467 996740533 654122259 952582646 462122708 822617887 719807149 652868728 540199241 775391235 964629540 666906117 49147244 378995471 359298223 779429127 10675845 225809632 948339993 754251154 151701887 570959698 501626665 811123868 368689126 587486678 162405695 378552915 340794359 523935416 362089968 178057941 51408127 400073262 546813689 73873838 534042336 374880050 728603959 240822423 145701987 53462928 3334134 402868052 376706864 453204360 703953077 421667328 900539254 796206265 634898127 86871864 474367623 19450233 880571859 254307430 569190225 348817940 83878504 292570439 861362826 51119979 984722794 112673450 849850459 426683725 517185246 70673058 113573595 4958218 627741876 803740235 891001184 836201357 993639980 670361304 47841207 89515313 564594300 837502715 387126580 801354060 940791110 653818359 882106325 629089204 454855233 149950852 92725618 982348481 442640222 520277829 38739721 535861292 591538698 627689740 425463902 638079432 49881504 825764355 54126431 262201414 917965246 405228410 617557202 279296102 99030863 565292416 555199192 12191580 477229175 657756035 362216388 726922301 295800410 213412483 355599496 10587567 222163893 112673098 952031639 479725112 996911719 992731748 829904377 534055679 490532420 134124120 443497981 574013195 293514514 382472546 509514743 289147369 801586001 168049094 691322552 422647945 789151303 956877737 687144977 611600372 26645164 214164772 192356418 947033035 365368351 525347875 758133612 313058773 727146942 18274513 267460268 93978856 132438433 364751553 603234429 566695237 295122498 239917767 90436877 783977638 547943262 882331303 180856479 536478683 838339498 462325284 895451933 496919932 784931456 922553505 760810937 172249786 564953408 703519261 821098763 823779593 928772468 454058519 390883355 601594325 121459876 303919165 83438440 476002185 399000240 100151551 941024903 268441497 262357258 91910224 727988422 12772852 673586708 28160824 654947509 195434129 663855193 676348129 369386149 596317796 723850727 753205673 299657777 326240348 967041622 837329491 227775649 825526101 817395386 814053017 256705958 681021047 777643696 615053258 901394503 495400721 606316045 628009596 252013838 69341565 296596620 266936901 742427431 152482454 815935028 450364220 965378773 945103633 700456421 614212826 922978737 32122559 565634296 162278529 751166314 777781696 609962582 804483042 990440407 265151588 178111898 290945928 211668668 799417648 522068015 646010589 237856802 425656994 861256 559327598 875707766 663716858 626146472 546571083 367544438 976191906 544557323 720889439 240622536 891598244 527649273 264129713 216706242 865896184 989230321 128203 609728340 51320577 528835627 278008541 315682700 992181122 564848474 975993322 152746219 168987901 857459852 683243850 124097362 119668481 557757687 933655858 562715003 282763195 856319123 76715882 960502403 709846096 708724431 558702364 225645330 317157598 977506747 418935769 552422331 335419660 421766773 697867162 417655249 189071802 633488105 713088618 674731544 163962377 456608067 930740812 107136103 676495142 48838083 262393217 53538467 197560633 451249961 851328085 654755126 814199536 208576428 760513856 520940020 846914513 225091655 754276273 481407537 783594941 312870803 192913605 521629708 337861055 621745264 181906453 671341385 892679603 390766437
